package com.example;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;


/**
 * @Author loubobooo
 * @Description #4. 寻找两个正序数组的中位数
 * @Date 2022/2/21
 */
public class MedianOfTwoSortedArrays {

    /**
     * 方法描述:给定两个大小分别为 m 和 n 的正序（从小到大）数组nums1 和nums2。请你找出并返回这两个正序数组的 中位数 。
     * 算法的时间复杂度应该为 O(log (m+n)) 。
     * 示例 1：
     *
     * 输入：nums1 = [1,3], nums2 = [2]
     * 输出：2.00000
     * 解释：合并数组 = [1,2,3] ，中位数 2
     * @param: [nums1, nums2]
     * @return: double
     * @author: loubobooo
     * @date: 2022/2/21
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums1.length; i++) {
            list.add(nums1[i]);
        }
        for (int i = 0; i < nums2.length; i++) {
            list.add(nums2[i]);
        }
        list.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });
        // 奇数
        return (list.size() & 1) == 1 ? list.get(list.size() / 2) : (list.get(list.size() / 2 -1) + list.get(list.size() / 2))/2.0;
    }
}
